package algorithm.leetcode;

import algorithm.templates.ListNode;

public class NO160_相交链表 {

    class PerformanceSolution {
        // 总路程一致，所以最侯总会同时到达相交点
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode pa = headA, pb = headB;
            while (pa != pb) {
                pa = pa.next != null ? pa.next : headB;
                pb = pb.next != null ? pb.next : headA;
            }
            return pa;
        }
    }

    class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int lengthA = 0, lengthB = 0;
            ListNode tempA = headA, tempB = headB;
            while (tempA != null || tempB != null) {
                if (tempA != null) {
                    lengthA++;
                    tempA = tempA.next;
                }
                if (tempB != null) {
                    lengthB++;
                    tempB = tempB.next;
                }
            }
            // A = 5 B = 6
            System.out.println("lengthA = " + lengthA);
            System.out.println("lengthB = " + lengthB);

            while (lengthA > lengthB) {
                headA = headA.next;
                lengthA--;
            }

            while (lengthB > lengthA) {
                headB = headB.next;
                lengthB--;
            }

            while (headA != null && headB != null) {
                if (headA == headB) {
                    return headA;
                }
                headA = headA.next;
                headB = headB.next;
            }
            return null;
        }
    }
}
